package org.example.BinaryTree;

import java.util.ArrayList;

public class Verify_binary_search_tree {
    public static ArrayList<Integer> arr = new ArrayList<>();
    public static TreeNode max;

    public static void main(String[] args) {
        //验证二叉搜索树

        //给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
        //有效 二叉搜索树定义如下：
        //节点的左子树只包含 小于 当前节点的数。
        //节点的右子树只包含 大于 当前节点的数。
        //所有左子树和右子树自身必须也是二叉搜索树。
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(7);
        TreeNode node3 = new TreeNode(1);
        TreeNode node4 = new TreeNode(3);
        TreeNode root = new TreeNode(4);
        TreeNode node9 = new TreeNode(9);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node9;
        System.out.println(isValidBST2(root));
    }

    //直接在递归中判断，本质上还是中序遍历
    public static boolean isValidBST2(TreeNode root) {
        if (root == null) return true;
        //判断左节点
        boolean left = isValidBST2(root.left);
        if (!left) return false;
        //判断中节点
        if (max != null && max.val >= root.val) return false;
        max = root;
        //判断右节点
        boolean right = isValidBST2(root.right);
        return right;
    }

    //判断数组是否是从小到大排列
    public static boolean isValidBST(TreeNode root) {
        get(root);

        for (int i = 0; i < arr.size() - 1; i++) {
            if (arr.get(i) >= arr.get(i + 1)) return false;
        }
        return true;
    }

    //将二叉搜索树通过中序遍历添加到数组中
    public static void get(TreeNode root) {
        if (root == null) return;
        get(root.left);
        arr.add(root.val);
        get(root.right);
    }
}
